package com.fmm.medium;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BreadthFirstTraversal {

    /**
     * @param root 二叉树根节点
     * @return 二叉树按层遍历的结果
     * */
    public static List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<Object[]> queue = new LinkedList<>();
        int currentLevel = -1;
        queue.offer(new Object[]{root, 0});
        Object[] nodeObject;
        while ((nodeObject = queue.poll()) != null) {
            Node node = (Node) nodeObject[0];
            int level = (int) nodeObject[1];
            if (level != currentLevel) {
                currentLevel = level;
                List<Integer> levelList = new ArrayList<>();
                result.add(levelList);
                levelList.add(node.val());
            } else {
                result.get(level).add(node.val());
            }
            if (node.left() != null) {
                queue.offer(new Object[]{node.left(), level + 1});
            }
            if (node.right() != null) {
                queue.offer(new Object[]{node.right(), level + 1});
            }
        }
        return result;
    }

    private record Node(int val, Node left, Node right) {}
}
